package com.cty.C_SortAlgorithms.F_QuickSort;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/18 8:18
 * @Description: 快速排序  插入排序 + 三数据项取中 + 划分
 * @version: 1.0
 */
public class QuickSort2 {
    private int maxSize;
    private DataItem[] array;
    private int nItems;

    public QuickSort2(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nItems = 0;
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public int size(){
        return nItems;
    }

    public void displayArray(){
        for(int i=0; i<nItems; i++)
            System.out.print(array[i].getKey() + " ");
        System.out.println();
    }

    /**
     * 在数组尾部插入数据  O(1)
     * @param item
     * @return
     */
    public boolean insert(DataItem item){
        if(isFull())
            return false;

        array[nItems++] = item;
        return true;
    }


    /**
     * 问题1：小规模排序
     *      ① 手动排序
     *      ② 插入排序
     */

    /**
     * 交换
     * @param a
     * @param b
     */
    private void swap(int a, int b){
        DataItem temp = array[a].getItem();
        array[a].setItem(array[b]);
        array[b].setItem(temp);
    }

    /**
     * 小规模排序
     *      由于使用了 三数据项取中，划分不可处理数据项 <=3 的数据，堆小规模数据的排序可以使用：
     *          ① 手动排序：切割点 cutoff = 3
     *          ② 插入排序：切割点 cutoff = 9，最优切割点随机器、操作系统和编译器而变动
     */

    /**
     * 手动排序
     */
    private void manualSort(int left, int right){
        int num = right - left + 1;

        if(num <= 1)
            return;
        else if(num == 2){
            if(array[left].getKey() > array[right].getKey())
                swap(left, right);
        }else{
            if(array[left].getKey() > array[left+1].getKey())
                swap(left, left+1);
            if(array[left+1].getKey() > array[right].getKey())
                swap(left+1, right);
            if(array[left].getKey() > array[left+1].getKey())
                swap(left, left+1);
        }  // end else
    }  // end manualSort()

    /**
     * 插入排序
     * @param left
     * @param right
     */
    private void insertSort(int left, int right){
        int in, out;
        for(out=left+1; out<=right; out++){
            DataItem temp = array[out].getItem();
            in = out;
            while(in>left && array[in-1].getKey()>temp.getKey()){
                array[in].setItem(array[in-1]);
                in--;
            }
            array[in].setItem(temp);
        }  // end for
    }  // end insertSort()

    /**
     * 划分枢纽的选择：三数据项取中
     *      两端和中间三个数据项取中间值作为枢纽，并将三个中最小值移到左端，最大值移到右端
     *          优点：① 解决了数据偏逆序分布效率低的问题
     *                ② 取效了左端越界检查（左端小于枢纽，一定会停一下）
     * @param left
     * @param right
     * @return
     */
    private long medianOf3(int left, int right){
        int median = (left + right) / 2;

        // 将最小值放到left位置
        if(array[median].getKey() < array[left].getKey())
            swap(median, left);
        if(array[right].getKey() < array[left].getKey())
            swap(right, left);

        // 将最大值放到right位置
        if(array[median].getKey() > array[right].getKey())
            swap(median, right);

        // 将中值放到right-1位置
        swap(median, right-1);

        // 返回选择的枢纽值
        return array[right-1].getKey();
    }  // end medianOf3

    /**
     * 划分
     * @param left
     * @param right
     * @param pivot
     * @return
     */
    private int partition(int left, int right, long pivot){
        int leftPtr = left;
        int rightPtr = right - 1;

        while(true){
            while(array[++leftPtr].getKey() < pivot);  // 从左端开始，查找 关键字>=pivot 的数据项
            while(array[--rightPtr].getKey() > pivot);  // 从右端开始，查找 关键字<=pivot 的数据项

            if(leftPtr >= rightPtr)
                break;  // 指针交叉，划分结束
            else
                swap(leftPtr, rightPtr);
        }  // end while(true)

        swap(right-1, leftPtr);  // 将枢纽移到中间
        return leftPtr;  // 返回枢纽索引位置
    }  // end partition{}

    /**
     * 递归实现快速排序
     * @param left
     * @param right
     */
    private void recQuickSort(int left, int right){
        // 小规模排序
        int cutoff = 9;
//        int cutoff = 3;
        int num = right - left + 1;
        if(num <= cutoff)
            insertSort(left, right);  // 插入排序
//            manualSort(left, right);  // 手动排序
        else{  // 快速排序处理大划分
            // 划分
            long pivot = medianOf3(left, right);  // 三数据项取中选择枢纽
            int pivotIndex = partition(left, right, pivot);
            // 递归划分
            recQuickSort(left, pivotIndex-1);
            recQuickSort(pivotIndex+1, right);
        }  // end else
    }  // end recQuickSort()

    /**
     * 快速排序
     *      平均时间复杂度：  O(N*logN)    受数据分布影响小
     *      最好情况：        O(N*logN)
     *      最坏情况：        O(N*logN)
     *      空间复杂度：      O(logN)      递归造成栈空间的使用
     *      排序方式：                     内部排序
     *      稳定性：                       不稳定             存在跳跃式交换
     * 分析：
     *      每次划分近似于二分，约划分 log2(N)+1 次，每次划分约比较 N 次，交换小于 N/2 次
     *      假设比较和交换是最费时的操作，递归的调用和返回不增加额外的开销，则：
     *          比较次数：N*[log2(N)+1]
     *          交换次数：(N/2)*[log2(N)+1]
     */
    public void quickSort(){
        recQuickSort(0, nItems-1);
    }

}  // end QuickSort{}
